package org.example.algorithm.array;

import java.util.Arrays;

public class ThreeSumClosestSolution {

    public int threeSumClosest(int[] nums, int target) {
        int len = nums.length;
        Arrays.sort(nums);
        int minDistance = Integer.MAX_VALUE;
        boolean flag = true;
        for (int i=0;i<len-2;i++) {
            if (nums[i]+nums[i+1]+nums[i+2] >= target) {
                int lastMinDistance = minDistance;
                minDistance = Math.min(minDistance, Math.abs(nums[i]+nums[i+1]+nums[i+2]-target));
                if (lastMinDistance > minDistance) {
                    flag = true;
                }
                break;
            }
            if (nums[i]+nums[len-1]+nums[len-2] <= target) {
                int lastMinDistance = minDistance;
                minDistance = Math.min(minDistance, Math.abs(nums[i]+nums[len-1]+nums[len-2]-target));
                if (lastMinDistance > minDistance) {
                    flag = false;
                }
                continue;
            }
            int left = i+1;
            int right = len-1;
            while (left < right) {
                int tempSum = nums[i] + nums[left] + nums[right];
                int lastMinDistance = minDistance;
                minDistance = Math.min(minDistance, Math.abs(tempSum-target));
                if (minDistance < lastMinDistance) {
                    flag = (tempSum - target) > 0;
                }
                if (tempSum > target) {
                    right--;
                } else if(tempSum < target) {
                    left++;
                } else {
                    return target;
                }
            }
        }
        return flag ? target+minDistance : target-minDistance;
    }
}
